package algorithm;

import java.util.Arrays;

/**
 * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/implement-strstr
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class T00028 {
    public static void main(String[] args) {
        System.out.println(new Solution().strStr("ABABABC", "ABABC"));
    }

static class Solution {
    public int strStr(String haystack, String needle) {
        if(needle == null || needle.length() == 0)
            return 0;
        final int lh, ln;
        if(haystack == null || (lh = haystack.length()) == 0 || lh < (ln = needle.length()))
            return -1;
        KMS kms = new KMS(needle);
        return kms.search(haystack);
    }

    private static class KMS {
        private final String ptx;
        private final int len;
        private final int[][] dp;

        public KMS(String ptx) {
            this.ptx = ptx;
            len = ptx.length();
            dp = new int[len][256];
            dp[0][ptx.charAt(0)] = 1; // 第一个元素匹配进入状态1
            int x = 0; // 影子状态，初始为0
            for (int i = 1; i < len; i++) {
                char c = ptx.charAt(i);
                int j = 0;
                for (; j < 256; j++) {
                    if(c == j)
                        dp[i][j] = i + 1;
                    else
                        dp[i][j] = dp[x][j];
                }
                x = dp[x][c];
            }
//            for (int i = 0; i < dp.length; i++) {
//                System.out.println(Arrays.toString(dp[i]));
//            }
        }

        public int search(String txt) {
            int s = 0; // 初始状态
            for (int i = 0; i < txt.length(); i++) {
                s = dp[s][txt.charAt(i)];
                if(s == len)
                    return i - len + 1;
            }
            return -1;
        }
    }
}
}